package com.hainiu.cat.sort.write;

/**
 * create by biji.zhao on 2021/5/30
 */

import com.hainiu.cat.util.SortUtil;

/**
 * 快速排序算法实现
 */
public class QuickSorting {

    public static void main(String[] args) {
        int[] sortArray = {1, 20, 3, 5, 7, 30, 47, 28, 10};
        SortUtil.arrayToString(sortArray);
        sorting(sortArray, 0, sortArray.length - 1);
        SortUtil.arrayToString(sortArray);
    }

    private static void sorting(int[] array, int start, int end) {
        if (array.length == 0 || start >= end) {
            return;
        }
        int key = array[start];
        int i = start;
        int j = end;

        while (i < j) {
            // 先让后指针往前移动，找到第一个比基数小的
            while (array[j] >= key && i < j) {
                j -- ;
            }
            // 再让前指针往后移动，找到第一个比基数大的
            while (array[i] <= key && i < j) {
                i ++;
            }
            // 找到后交换
            if (i < j) {
                SortUtil.swap(array, i, j);
            }
        }
        // 再让基数和i下表位置换一下
        array[start] = array[i];
        array[i] = key;
        // 每一轮操作只是确保了左侧都比基数key小，右侧都比基数大
        sorting(array, start, i - 1);
        sorting(array, i + 1, end);
    }

}
